package data_structs;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.TreeMap;

public class HashTable<E> {

	/**
	 * 
	 * @author DC
	 *
	 * @param <E>
	 * Only used during resizing of the hash table
	 */
	private class HashIterator<E> implements Iterator<E> {
		private int arrIndex;
		private int listIndex;
		private int objsLeft;
		private ArrayList<E> currList;
		private String currKey;
		
		public HashIterator() {
			arrIndex = 0;
			objsLeft = numObjects;
			while( hashArr[arrIndex].size() == 0 )
				hashArr[arrIndex++] = null;
			currKey = hashArr[arrIndex].lastKey();
			currList = (ArrayList<E>) hashArr[arrIndex].get(currKey);
			listIndex = currList.size()-1;
		}
		
		public boolean hasNext() {
			return objsLeft != 0;
		}
		
		public E next() {
			if( listIndex < 0 ) {
				hashArr[arrIndex].remove(currKey);
				while( hashArr[arrIndex].size() == 0 )
					hashArr[arrIndex++] = null;
				currKey = hashArr[arrIndex].lastKey();
				currList = (ArrayList<E>) hashArr[arrIndex].get(currKey);
				listIndex = currList.size()-1;
			}
			
			E ret = currList.get(listIndex);
			currList.remove(listIndex--);
			objsLeft--;
			return ret;
		}
		
		public void remove() {
			throw new UnsupportedOperationException("Remove not allowed.");
		}
	}
	
	//Global variables
	private TreeMap<String,ArrayList<E>>[] hashArr;
	private int tableSize;
	private int numObjects;
	private int numOfResize = 0;
	private static double maxLoadFactor = 0.75;
	
	public HashTable() {
		this(9973);
	}
	
	public HashTable(int tableSize) {
		
		if( tableSize <= 0) {
			this.tableSize = 9973;
			System.err.println("Table size must be a positive integer. Setting to 9973.");
		}
		else
			this.tableSize = tableSize;
		numObjects = 0;
		hashArr = new TreeMap[tableSize];
		for( int i = 0; i < tableSize; i++ )
			hashArr[i] = new TreeMap();
	}
	
	public boolean add(E obj) {
//		if( isFull() )
//			resize();
		
		int index = (obj.hashCode() & 0x7FFFFFFF) % tableSize;
		TreeMap<String,ArrayList<E>> tree = hashArr[index];
		//Check if object does not already exists
		if( !tree.containsKey(obj.toString()) ) {
			ArrayList<E> list = new ArrayList<E>();
			list.add(obj);
			tree.put(obj.toString(), list);
		}
		else {
			ArrayList<E> list = tree.get(obj.toString());
			list.add(obj);
		}
		numObjects++;
		return true;
	}

	//Return the list of found objects' toString
	public ArrayList<E> contains(E obj) {
		if( isEmpty() )
			return null;
		
		int index = (obj.hashCode() & 0x7FFFFFFF) % tableSize;
		TreeMap<String,ArrayList<E>> tree = hashArr[index];
		
		ArrayList<E> list = tree.get(obj.toString());
		return list;
	}

	public void resize() {
		//Resize info
		numOfResize++;
		System.out.println("Resize #"+numOfResize+"\nTableSize before resize: "+tableSize+"\n" +
				"LoadFactor: "+loadFactor()+"\nNumber of elements: "+numObjects+"\n");
		System.out.println("Memory left over: "+java.lang.Runtime.getRuntime().freeMemory());
		
		//Copy elements with iterator
		HashIterator<E> iter = new HashIterator();
		
		
		//Double the table size then increment to a semi-prime number
		//If can be divided by any first six prime numbers
		//evenly, increment by 1
		tableSize <<= 1;
		while( tableSize % 2 == 0 || tableSize % 3 == 0 || tableSize % 5 == 0
				|| tableSize % 7 == 0 || tableSize % 9 == 0 || tableSize % 11 == 0 )
					tableSize++;
		
		TreeMap<String,ArrayList<E>>[] tmp = new TreeMap[tableSize];
		for( int i = 0; i < tableSize; i++ )
			tmp[i] = new TreeMap();
		
		while( iter.hasNext() ) {
			E obj = iter.next();
			int index = (obj.hashCode() & 0x7FFFFFFF) % tableSize;
			TreeMap<String,ArrayList<E>> tree = tmp[index];
			if( !tree.containsKey(obj.toString()) ) {
				ArrayList<E> list = new ArrayList<E>();
				list.add(obj);
				tree.put(obj.toString(), list);
			}
			else {
				ArrayList<E> list = tree.get(obj.toString());
				list.add(obj);
			}
		}
		
		hashArr = tmp;
		System.out.println("Load Factor after resize: "+loadFactor()+"\n");
	}

	public E remove(E obj) {
		throw new UnsupportedOperationException("Remove not allowed.");
	}

	public TreeMap<String,ArrayList<E>>[] allElements() {
		return hashArr;
	}

	public double loadFactor() {
		return (double) numObjects/tableSize;
	}

	public int numObjects() {
		return numObjects;
	}

	public boolean isEmpty() {
		return numObjects == 0;
	}

	public boolean isFull() {
		return loadFactor() >= maxLoadFactor;
	}
	
	//Print out info about hash table
	public String hashStatus() {
		int zero, least5, least10, least100, more100;
		zero = least5 = least10 = least100 = more100 = 0;
		for( int i = 0; i < tableSize; i++ ) {
			int num = hashArr[i].size();
			if( num == 0 ) zero++;
			else if( num <= 5 ) least5++;
			else if( num <= 10 ) least10++;
			else if( num <= 100 ) least100++;
			else more100++;
		}
		double pctNotUsed = (double) zero/tableSize*100;
		return "***HASH STATUS***\n$" +
				"Trees with no items: "+zero+"\n$" +
				"Trees with 1 to 5 items: "+least5+"\n$" +
				"Trees with 6 to 10 items: "+least10+"\n$" +
				"Trees with 11 to 100 items: "+least100+"\n$" +
				"Trees with more than 100 items: "+more100+"\n$" +
				"Table Size: "+tableSize+"\n$" +
				"Percentage not in use: "+pctNotUsed+"%\n$" +
				"Current Load Factor: "+loadFactor()+"\n$" +
				"Number of resizes: "+numOfResize+"\n";
	}
}
